{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Provinces"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findCircleNum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #省份数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>有 <code>n</code> 个城市，其中一些彼此相连，另一些没有相连。如果城市 <code>a</code> 与城市 <code>b</code> 直接相连，且城市 <code>b</code> 与城市 <code>c</code> 直接相连，那么城市 <code>a</code> 与城市 <code>c</code> 间接相连。</p>\n",
    "\n",
    "<p><strong>省份</strong> 是一组直接或间接相连的城市，组内不含其他没有相连的城市。</p>\n",
    "\n",
    "<p>给你一个 <code>n x n</code> 的矩阵 <code>isConnected</code> ，其中 <code>isConnected[i][j] = 1</code> 表示第 <code>i</code> 个城市和第 <code>j</code> 个城市直接相连，而 <code>isConnected[i][j] = 0</code> 表示二者不直接相连。</p>\n",
    "\n",
    "<p>返回矩阵中 <strong>省份</strong> 的数量。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/24/graph1.jpg\" style=\"width: 222px; height: 142px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>isConnected = [[1,1,0],[1,1,0],[0,0,1]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/24/graph2.jpg\" style=\"width: 222px; height: 142px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>isConnected = [[1,0,0],[0,1,0],[0,0,1]]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 200</code></li>\n",
    "\t<li><code>n == isConnected.length</code></li>\n",
    "\t<li><code>n == isConnected[i].length</code></li>\n",
    "\t<li><code>isConnected[i][j]</code> 为 <code>1</code> 或 <code>0</code></li>\n",
    "\t<li><code>isConnected[i][i] == 1</code></li>\n",
    "\t<li><code>isConnected[i][j] == isConnected[j][i]</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-provinces](https://leetcode.cn/problems/number-of-provinces/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-provinces](https://leetcode.cn/problems/number-of-provinces/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,0],[1,1,0],[0,0,1]]', '[[1,0,0],[0,1,0],[0,0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        seen = set()\n",
    "        res = 0\n",
    "        for i in range(len(isConnected)):\n",
    "            if i not in seen:\n",
    "                toSee = [i]\n",
    "                while len(toSee):\n",
    "                    cur = toSee.pop()\n",
    "                    if cur not in seen:\n",
    "                        seen.add(cur)\n",
    "                        toSee += [nei for nei,val in enumerate(isConnected[cur]) if val and nei not in seen] \n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M):\n",
    "        \"\"\"\n",
    "        :type M: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = len(M)\n",
    "        ufset = [i for i in range(l)]\n",
    "\n",
    "        def find( i):\n",
    "            rec = i\n",
    "            while True:\n",
    "                tmp = ufset[rec]\n",
    "                if tmp == rec:\n",
    "                    return rec\n",
    "                else:\n",
    "                    rec = tmp\n",
    "\n",
    "        def union(i, j):\n",
    "            i_set = find(i)\n",
    "            j_set = find(j)\n",
    "            if i_set == j_set:\n",
    "                return 0\n",
    "\n",
    "            if i_set < j_set:\n",
    "                c_set = i_set\n",
    "                c = j\n",
    "            else:\n",
    "                c_set = j_set\n",
    "                c = i\n",
    "\n",
    "            rec = c\n",
    "            while True:\n",
    "                tmp = ufset[rec]\n",
    "                ufset[rec] = c_set\n",
    "                if tmp == rec:\n",
    "                    return 1\n",
    "                else:\n",
    "                    rec = tmp\n",
    "\n",
    "        res = l\n",
    "        for i in range(l-1):\n",
    "            for j in range (i+1,l):\n",
    "                if M[i][j] == 1:\n",
    "                    res -= union(i,j)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M):\n",
    "        \"\"\"\n",
    "        :type M: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        N = len(M)\n",
    "        ids = [i for i in range(N)]\n",
    "        res = N\n",
    "        \n",
    "        def union(ids, res, i, j):\n",
    "            pi, pj = find(ids, i), find(ids, j)\n",
    "            if pi != pj:\n",
    "                res -= 1\n",
    "                ids[pi] = pj\n",
    "            return ids, res\n",
    "        \n",
    "        def find(ids, i):\n",
    "            while ids[i] != i:\n",
    "                ids[i] = ids[ids[i]]\n",
    "                i = ids[i]\n",
    "            return i\n",
    "        \n",
    "        for i in range(1, N):\n",
    "            for j in range(i):\n",
    "                if M[i][j] == 1:\n",
    "                    ids, res = union(ids, res, i, j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import *\n",
    "class Solution:\n",
    "    def findCircleNum(self, M):\n",
    "        \"\"\"\n",
    "        :type M: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        count=0\n",
    "        m=len(M)\n",
    "        visit=[False]*m\n",
    "        for i in range(m):\n",
    "            if visit[i]==False:\n",
    "                count+=1\n",
    "                visit[i]=True  \n",
    "                q=Queue()\n",
    "                q.put(i)\n",
    "                while not q.empty():\n",
    "                    i=q.get()\n",
    "                    for j in range(m):\n",
    "                        if j!=i and visit[j]==False and M[i][j]==1:\n",
    "                            visit[j]=True\n",
    "                            q.put(j)\n",
    "        return count\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import *\n",
    "class Solution:\n",
    "    def findCircleNum(self, M):\n",
    "        \"\"\"\n",
    "        :type M: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        count=0\n",
    "        m=len(M)\n",
    "        visit=[False]*m\n",
    "        for i in range(m):\n",
    "            if visit[i]==False:\n",
    "                count+=1\n",
    "                visit[i]=True  \n",
    "                q=Queue()\n",
    "                q.put(i)\n",
    "                while not q.empty():\n",
    "                    i=q.get()\n",
    "                    for j in range(m):\n",
    "                        if visit[j]==False and M[i][j]:\n",
    "                            visit[j]=True\n",
    "                            q.put(j)\n",
    "        return count\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self,us,i):\n",
    "        while us[i]!=i:\n",
    "            i=us[i]\n",
    "        return i\n",
    "    def join(self,us,i,j):\n",
    "        us[self.find(us,j)]=self.find(us,i)\n",
    "    def findCircleNum(self, M: List[List[int]]) -> int:\n",
    "        us=[i for i in range(len(M))]\n",
    "        for i in range(len(M)-1):\n",
    "            for j in range(i+1,len(M)):\n",
    "                if M[i][j]==1:\n",
    "                    self.join(us,i,j)\n",
    "        sum=[]\n",
    "        for i in range(len(M)):\n",
    "            t=self.find(us,i)\n",
    "            if t not in sum:\n",
    "                sum.append(t)\n",
    "        return len(sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M: 'List[List[int]]') -> 'int':\n",
    "        n = len(M)\n",
    "        visited = [0]*n\n",
    "        res = 0\n",
    "        \n",
    "        def dfs(i):\n",
    "            for j in range(n):\n",
    "                if M[i][j] and visited[j] == 0:\n",
    "                    visited[j] = 1\n",
    "                    dfs(j)\n",
    "                \n",
    "        for i in range(n):\n",
    "            if visited[i] == 0:\n",
    "                dfs(i)\n",
    "                res += 1\n",
    "                \n",
    "        return res\n",
    "               \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M):\n",
    "        \"\"\"\n",
    "        :type M: List[List[int]]\n",
    "        :rtype: int\n",
    "        \n",
    "        N = len(M)\n",
    "        num = [0] * N\n",
    "        frinds = []\n",
    "        for i in range(N): \n",
    "            if all(M[i][j] == 0 for j in range(i)) and all(M[i][j] == 0 for j in range(i + 1, N)):\n",
    "                num[i] = 1\n",
    "        print(num)\n",
    "        if all(i == 0 for i in num):\n",
    "            return 1\n",
    "        last = num[0]\n",
    "        circle = 1 if last == 1 else 0\n",
    "        for i in range(1,N):\n",
    "            if num[i] == 0:\n",
    "                last = 0\n",
    "                continue\n",
    "            else:\n",
    "                if last == 0 and num[i] == 1:\n",
    "                    circle += 2\n",
    "                elif last == 1 and num[i] == 1:\n",
    "                    circle += 1\n",
    "                last = 1\n",
    "        return circle\n",
    "        \"\"\"\n",
    "        num = []\n",
    "        for i in M:\n",
    "            new = set()\n",
    "            for j in range(len(i)):\n",
    "                if i[j] == 1:\n",
    "                    new.add(j)\n",
    "            num.append(new)\n",
    "        #print(num)\n",
    "        res = self.recursive(num)\n",
    "        return len(res)\n",
    "    def recursive(self, num):\n",
    "        res = []\n",
    "        visited = [0] * len(num)\n",
    "        for i in range(len(num)):\n",
    "            if visited[i] != 0:\n",
    "                continue\n",
    "            new = num[i]\n",
    "            for j in range(i + 1,len(num)):\n",
    "                if num[j] & new and visited[j] == 0:\n",
    "                    new = num[j] | new\n",
    "                    visited[j] = 1\n",
    "            res.append(new)\n",
    "        #print(res,visited,len(res))\n",
    "        if len(res) == 1 or all(i == 0 for i in visited):\n",
    "            #print(res)\n",
    "            return res\n",
    "        else:\n",
    "            return self.recursive(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M):\n",
    "        \"\"\"\n",
    "        :type M: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "        n = len(M)\n",
    "        set1 = set()\n",
    "        ans = 0\n",
    "        set2 = set()\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                if M[i][j] == 1:\n",
    "                    M[i][j] = 0\n",
    "                    # if j not in set2:\n",
    "                    set1.add((i,j))\n",
    "                        # set2.add(j)\n",
    "                    ans += 1\n",
    "\n",
    "                while set1:\n",
    "                    q,w= set1.pop()\n",
    "                    for e in range(n):\n",
    "                        if M[w][e] == 1:\n",
    "                            set1.add((w,e))\n",
    "                            M[w][e] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M):\n",
    "        \"\"\"\n",
    "        :type M: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(M)\n",
    "        lst = []\n",
    "        for i in range(length):\n",
    "            for j in range(i,length):\n",
    "                if M[i][j] == 1:\n",
    "                    t = set()\n",
    "                    t.add(i)\n",
    "                    t.add(j)\n",
    "                    lst.append(t)\n",
    "        lst1 = [lst[0]]\n",
    "        count = len(lst)\n",
    "        while True:\n",
    "            for m in lst:\n",
    "                flag = 0\n",
    "                for n in range(len(lst1)):\n",
    "                    if m & lst1[n]:\n",
    "                        lst1[n] = m|lst1[n]\n",
    "                        flag = 1\n",
    "                if flag == 0:\n",
    "                    lst1.append(m)\n",
    "            if count == len(lst1):\n",
    "                break\n",
    "            count = len(lst1)\n",
    "            lst = lst1\n",
    "            lst1 = [lst[0]]\n",
    "        return len(lst1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding:utf-8 -*-\n",
    "import pdb\n",
    "class Solution:\n",
    "    def dfs(self,visited,M,i):\n",
    "        if(visited[i]==True):\n",
    "            return None\n",
    "        queue = []\n",
    "        queue.append(i)\n",
    "        visited[i] = True\n",
    "        while queue:\n",
    "            num = queue.pop(0)\n",
    "            for j in range(len(M)):\n",
    "                if(M[num][j]==1 and visited[j]==False):\n",
    "                    visited[j] = True\n",
    "                    queue.append(j)\n",
    "\n",
    "        return visited\n",
    "    def findCircleNum(self, M):\n",
    "        \"\"\"\n",
    "        :type M: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count =0\n",
    "        visited = [False for _ in range(len(M))]\n",
    "        for i in range(len(M)):\n",
    "            if(visited[i]==True):\n",
    "                continue\n",
    "            res =self.dfs(visited,M,i)\n",
    "            if(res!=None):\n",
    "                visited = res\n",
    "                count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M: List[List[int]]) -> int:\n",
    "        length = len(M)\n",
    "        parent = [i for i in range(length)]\n",
    "        count = length\n",
    "        for i in range(length):\n",
    "            for j in range(length):\n",
    "                if M[i][j] == 1:\n",
    "                    count = self.union(parent, i, j, count)\n",
    "        return count\n",
    "\n",
    "    def find(self, parent, i):\n",
    "        root = i\n",
    "        while root != parent[root]:\n",
    "            root = parent[root]\n",
    "        return root\n",
    "    \n",
    "    def union(self, parent, i, j, count):\n",
    "        parent_i = self.find(parent, i)\n",
    "        parnet_j = self.find(parent, j)\n",
    "        if parent_i != parnet_j:\n",
    "            parent[parent_i] = parnet_j\n",
    "            count -= 1\n",
    "        return count\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self,M,i,flag):\n",
    "        for j in range(len(M)):\n",
    "            if M[i][j] == 1 and flag[j]==False:\n",
    "                flag[j] = True\n",
    "                self.dfs(M,j,flag)\n",
    "    \n",
    "    def findCircleNum(self, M: List[List[int]]) -> int:\n",
    "        N = len(M)\n",
    "        flag = [False for _ in range(N)]\n",
    "        count = 0\n",
    "        for i in range(N):\n",
    "            if flag[i]==False:\n",
    "                count +=1\n",
    "                self.dfs(M,i,flag)\n",
    "        return count\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        def findCircleNumDFS(grid, visted, k):\n",
    "            visted[k] = True\n",
    "            for idx in range(len(grid)):\n",
    "                if grid[k][idx] == 0 or visted[idx]:\n",
    "                    continue\n",
    "                findCircleNumDFS(grid, visted, idx)\n",
    "                \n",
    "\n",
    "        cnt = 0\n",
    "        viste = [False]*len(grid)\n",
    "        for i in range(len(grid)):\n",
    "           if not viste[i]:\n",
    "               cnt+=1\n",
    "               findCircleNumDFS(grid,viste,i)\n",
    "\n",
    "        return cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M: List[List[int]]) -> int:\n",
    "        nodesnum = len(M)\n",
    "        parent = list(range(nodesnum))\n",
    "        ans = len(M)\n",
    "        def find(x):\n",
    "            nonlocal parent\n",
    "            if parent[x]==x:\n",
    "                return x\n",
    "            return find(parent[x])\n",
    "        \n",
    "        def union(x,y):\n",
    "            nonlocal ans\n",
    "            if find(x) != find(y):\n",
    "                parent[find(x)] = parent[find(y)]\n",
    "                ans -= 1\n",
    "\n",
    "        for i in range(nodesnum):\n",
    "            for j in range(i+1,nodesnum):\n",
    "                if M[i][j] == 1:\n",
    "                    union(i,j)\n",
    "\n",
    "        \n",
    "\n",
    "        return ans\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = {i:i for i in range(n)}\n",
    "        self.size = n\n",
    "        \n",
    "    def find(self, x):\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        # print(x, self.parent[x])\n",
    "        return self.parent[x]\n",
    "        \n",
    "    def union(self, x, y):\n",
    "        px, py = self.find(x), self.find(y)\n",
    "        if px != py:\n",
    "            self.parent[px] = py\n",
    "            \n",
    "    def cnt(self):\n",
    "        res = 0\n",
    "        for i in range(self.size):\n",
    "            if self.parent[i] == i:\n",
    "                res += 1\n",
    "                \n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M: List[List[int]]) -> int:\n",
    "        if not M:\n",
    "            return 0\n",
    "        \n",
    "        uf = UnionFind(len(M))\n",
    "        for i in range(len(M)):\n",
    "            for j in range(i):\n",
    "                if M[i][j] == 1:\n",
    "                    uf.union(i, j)\n",
    "        # print(uf.parent) \n",
    "        return uf.cnt()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, idx):\n",
    "        while idx in self.union:\n",
    "            idx = self.union[idx]\n",
    "        return idx\n",
    "    def findCircleNum(self, M: List[List[int]]) -> int:\n",
    "        self.union = {}\n",
    "        n = len(M)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if M[i][j] == 0:\n",
    "                    continue\n",
    "                root_i = self.findRoot(i)\n",
    "                root_j = self.findRoot(j)\n",
    "                if root_i != root_j:\n",
    "                    self.union[root_i] = root_j\n",
    "        roots = set()\n",
    "        for i in range(n):\n",
    "            root = self.findRoot(i)\n",
    "            roots.add(root)\n",
    "        return len(roots)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M: List[List[int]]) -> int:\n",
    "        visited = [False for _ in range(len(M))]\n",
    "        count = 0\n",
    "        for i in range(len(M)):\n",
    "            if not visited[i]:\n",
    "                self.dfs(M, i, visited)\n",
    "                count += 1\n",
    "        return count\n",
    "\n",
    "    def dfs(self, M, j, visited):\n",
    "        visited[j] = True\n",
    "        for i in range(len(M)):\n",
    "            if visited[i] == False and M[j][i]==1:\n",
    "                self.dfs(M, i, visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFriend(self, M, i, j):\n",
    "        queue = [[i, j]]\n",
    "        M[i][j] = 0\n",
    "        M[j][i] = 0\n",
    "        while queue:\n",
    "            x, y = queue.pop(0)\n",
    "            M[y][y] = 0\n",
    "            M[x][x] = 0\n",
    "            # print(x, y, M)\n",
    "            for k in range(len(M[0])):\n",
    "                # print(x, y, k, M[x][k])\n",
    "                if k != y and k != x and M[y][k] == 1:\n",
    "                    # print(\"in\")\n",
    "                    queue.append([y, k])\n",
    "                    M[y][k] = 0\n",
    "                    M[k][y] = 0\n",
    "                    # print(M, \"queue: \", queue)\n",
    "        # print(M)\n",
    "        \n",
    "\n",
    "\n",
    "    def findCircleNum(self, M: List[List[int]]) -> int:\n",
    "        n = len(M)\n",
    "        m = len(M[0])\n",
    "        count = 0\n",
    "        # M[0][0] = 0\n",
    "        for i in range(n):\n",
    "            for j in range(0, i + 1):\n",
    "                if M[i][j] == 1:\n",
    "                    count += 1\n",
    "                    # print(i, j, count)\n",
    "                    self.findFriend(M, i, j)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M: List[List[int]]) -> int:\n",
    "        N = len(M)\n",
    "        if len(M) < 2:\n",
    "            return len(M)\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            for j in range(N):\n",
    "                if M[i][j] == 1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "\n",
    "        for i in range(N):\n",
    "            if i not in visited:\n",
    "                count += 1\n",
    "                visited.add(i)\n",
    "                dfs(i)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M: List[List[int]]) -> int:\n",
    "        N = len(M)\n",
    "        count = 0\n",
    "        visited = set()\n",
    "        \n",
    "        def dfs(i):\n",
    "            for j in range(N):\n",
    "                if M[i][j] and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        \n",
    "        for i in range(N):\n",
    "            if  i not in visited:\n",
    "                count += 1\n",
    "                visited.add(i)\n",
    "                dfs(i)\n",
    "        \n",
    "        return count \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "        # 额外记录集合的数量\n",
    "        self.num_of_sets = 0\n",
    "    \n",
    "    def find(self,x):\n",
    "        root = x\n",
    "        \n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "        \n",
    "        while x != root:\n",
    "            original_father = self.father[x]\n",
    "            self.father[x] = root\n",
    "            x = original_father\n",
    "        \n",
    "        return root\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "            # 集合的数量-1\n",
    "            self.num_of_sets -= 1\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "            # 集合的数量+1\n",
    "            self.num_of_sets += 1\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, M: List[List[int]]) -> int:\n",
    "        uf = UnionFind()\n",
    "        for i in range(len(M)):\n",
    "            uf.add(i)\n",
    "            for j in range(i):\n",
    "                if M[i][j]:\n",
    "                    uf.merge(i,j)\n",
    "        \n",
    "        return uf.num_of_sets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind(object):\n",
    "    def __init__(self,n) -> None:\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "    def find(self,p):\n",
    "        while p != self.parent[p]:\n",
    "            p = self.parent[p]\n",
    "        return p\n",
    "    def union(self,p,q):\n",
    "        if self.find(p) != self.find(q):\n",
    "            self.parent[self.find(p)] = self.find(q)\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: list[list[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        uf = UnionFind(n)\n",
    "        for r in range(n):\n",
    "            for c in range(r,n):\n",
    "                if isConnected[r][c] == 1:\n",
    "                    uf.union(r,c)\n",
    "        return len(set([uf.find(i) for i in range(n)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        # 深度优先\n",
    "        # cities = len(isConnected)\n",
    "        # visist = set()\n",
    "        # provinces = 0\n",
    "        # def dfs(i):\n",
    "        #     visist.add(i)\n",
    "        #     for j in range(cities):\n",
    "        #         if isConnected[i][j] == 1 and j not in visist:\n",
    "        #             dfs(j)\n",
    "        # for i in range(cities):\n",
    "        #     if i not in visist:\n",
    "        #         dfs(i)\n",
    "        #         provinces += 1\n",
    "        # return provinces\n",
    "\n",
    "        # 并查集        \n",
    "        n = len(isConnected)\n",
    "        fathers = {}\n",
    "        for i in range(n):\n",
    "            fathers[i] = i\n",
    "\n",
    "        def find(node):\n",
    "            if fathers[node] == node:\n",
    "                return node\n",
    "            else:\n",
    "                fathers[node] = find( fathers[node])\n",
    "                return fathers[node]\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j] == 1:\n",
    "                    left = find(i) \n",
    "                    right = find(j)\n",
    "                    if left != right:\n",
    "                        fathers[left] = right\n",
    "        for i in fathers:\n",
    "            find(i)\n",
    "        return len(set(fathers.values()))\n",
    "        \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        f = [i for i in range(len(isConnected))]\n",
    "        def find(x):\n",
    "            if x != f[x]:\n",
    "                f[x] = find(f[x])   \n",
    "            return f[x]         \n",
    "        for i in range(len(isConnected)):\n",
    "            isConnected[i][i] = 0\n",
    "            for j in range(len(isConnected)):\n",
    "                if isConnected[i][j] == 1:\n",
    "                    # isConnected[i][j] = isConnected[j][i] = 0\n",
    "                    f[find(i)] = find(j)\n",
    "        for i in range(len(f)):\n",
    "            f[i] = find(i)\n",
    "        return len(set(f))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def findCircleNum(self, M) -> int:\n",
    "#         father = [i for i in range(len(M))]\n",
    "\n",
    "#         def find(a):\n",
    "#             if father[a] != a: father[a] = find(father[a])\n",
    "#             return father[a]\n",
    "\n",
    "#         def union(a, b):\n",
    "#             father[find(b)] = find(a)\n",
    "#             # return find(b)\n",
    "\n",
    "#         for a in range(len(M)):\n",
    "#             for b in range(a):\n",
    "#                 if M[a][b]: union(a, b)\n",
    "#         for i in range(len(M)): find(i)\n",
    "#         return len(set(father))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        f = [i for i in range(len(isConnected))]\n",
    "        def find(x):\n",
    "            if(x == f[x]):\n",
    "                return x\n",
    "            else:\n",
    "                f[x] = find(f[x])\n",
    "                return f[x]       \n",
    "        for i in range(len(isConnected)):\n",
    "            isConnected[i][i] = 0\n",
    "            for j in range(len(isConnected)):\n",
    "                if isConnected[i][j] == 1:\n",
    "                    # isConnected[i][j] = isConnected[j][i] = 0\n",
    "                    f[find(i)] = find(j)\n",
    "        for i in range(len(f)):\n",
    "            f[i] = find(i)\n",
    "        \n",
    "        return len(set(f))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def findCircleNum(self, M) -> int:\n",
    "#         father = [i for i in range(len(M))]\n",
    "\n",
    "#         def find(a):\n",
    "#             if father[a] != a: father[a] = find(father[a])\n",
    "#             return father[a]\n",
    "\n",
    "#         def union(a, b):\n",
    "#             father[find(b)] = find(a)\n",
    "#             # return find(b)\n",
    "\n",
    "#         for a in range(len(M)):\n",
    "#             for b in range(a):\n",
    "#                 if M[a][b]: union(a, b)\n",
    "#         for i in range(len(M)): find(i)\n",
    "#         return len(set(father))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i: int):\n",
    "            for j in range(cities):\n",
    "                if isConnected[i][j] == 1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        \n",
    "        cities = len(isConnected)\n",
    "        visited = set()\n",
    "        provinces = 0\n",
    "\n",
    "        for i in range(cities):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                provinces += 1\n",
    "        \n",
    "        return provinces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        rows = len(isConnected)\n",
    "        cols = len(isConnected[0])\n",
    "        res = 0\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            for j in range(cols):\n",
    "                if isConnected[i][j] and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "\n",
    "        for i in range(rows):\n",
    "            if i not in visited:\n",
    "                res += 1\n",
    "                visited.add(i)\n",
    "                dfs(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        self.n = len(isConnected)\n",
    "        check_list = [False] * self.n\n",
    "        ans = 0\n",
    "        for i in range(self.n): #遍历每一个城市,i记录当前城市下标\n",
    "            if check_list[i] == False:  #判断每个没有被检查过的城市\n",
    "                q = deque()   #构建初始队列\n",
    "                q.append(i)   #把没有被检查过的城市放入队列中\n",
    "                check_list[i] = True #修改城市检查状态\n",
    "                #下面开始广搜，套模板\n",
    "                while q:#模板：如果队列中有元素\n",
    "                    cur_city = q.popleft()  #模板：弹出队列头部-当前城市\n",
    "                    for j in range(self.n): #遍历每一个城市,j记录下一个城市下标\n",
    "                        if check_list[j] == False and isConnected[cur_city][j] == 1 and cur_city != j:\n",
    "                            q.append(j)\n",
    "                            check_list[j] = True\n",
    "                #以上广搜过程结束\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        N = len(isConnected)\n",
    "        looked = set()\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for i in range(N):\n",
    "            if i not in looked:\n",
    "                res+=1\n",
    "                looked.add(i)\n",
    "                stack = [i]\n",
    "                while stack:\n",
    "                    u = stack.pop(0)\n",
    "                    for j in range(N):\n",
    "                        if isConnected[u][j] == 1 and j not in looked:\n",
    "                            stack.append(j)\n",
    "                            looked.add(j)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#DFS\n",
    "class Solution:\n",
    "    def dfs(self, isConnected, checkList, i):\n",
    "        # 对于传入的点i，将其标记为已检查过  \n",
    "        checkList[i] = 1\n",
    "        # 遍历其他点j\n",
    "        for j in range(self.n):\n",
    "            # 1. 若j点未检查过  2. 与i相连  3. j和i不是同一个点 \n",
    "            if checkList[j] == 0 and isConnected[i][j] == 1 and i != j:\n",
    "                # 对j进行DFS\n",
    "                self.dfs(isConnected, checkList, j)\n",
    "\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        # 获得城市数量\n",
    "        self.n = len(isConnected)\n",
    "        ans = 0\n",
    "        # 检查列表的长度是n\n",
    "        checkList = [0] * self.n\n",
    "\n",
    "        # 遍历每一个点i\n",
    "        for i in range(self.n):\n",
    "            # 如果该点没检查过， \n",
    "            if checkList[i] == 0:\n",
    "                # 则从点i出发，进行DFS    \n",
    "                self.dfs(isConnected, checkList, i)\n",
    "                # 做完本次DFS，省份数量+1\n",
    "                ans += 1            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        visited = set()\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                queue = [i]\n",
    "                visited.add(i)\n",
    "                while queue:\n",
    "                    node = queue.pop(0)\n",
    "                    for j, connected in enumerate(isConnected[node]):\n",
    "                        if connected and j not in visited:\n",
    "                            queue.append(j)\n",
    "                            visited.add(j)\n",
    "                ans += 1\n",
    "        return ans\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        parent = [i for i in range(n)]\n",
    "        #找到parent的parent pa_finpa\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        #将一个parfin和另一个fi连接起来,pafin_fin\n",
    "        def union(x,y):\n",
    "            parent[find(x)] = find(y)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                if isConnected[i][j]==1:\n",
    "                    union(i,j)\n",
    "        count = 0\n",
    "        for p in range(n):\n",
    "            if p == parent[p]:\n",
    "                count+=1\n",
    "        return count\n",
    "\n",
    "\n",
    "    # #pa_finpa\n",
    "    # def find(x):\n",
    "    #     if parent[x]!=x:\n",
    "    #         parent[x] = find(parent[x])\n",
    "    #     return parent[x]\n",
    "    # #pafin_fin\n",
    "    # def union(x,y):\n",
    "    #     parant[find(x)]=find(y)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        root = list(range(n))\n",
    "        def Find(x):\n",
    "            if x != root[x]:\n",
    "                root[x] = Find(root[x])\n",
    "            return root[x]\n",
    "        def Union(x,y):\n",
    "            root1 = Find(x)\n",
    "            root2 = Find(y)\n",
    "            root[root1] = root2\n",
    "            \n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if isConnected[i][j]:\n",
    "                    Union(i,j)\n",
    "        province = sum(root[i] == i for i in range(n))\n",
    "        return province"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        flag = [0] * n\n",
    "\n",
    "        def dfs(i):\n",
    "            flag[i] = 1\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j] == 1 and flag[j] == 0:\n",
    "                    dfs(j)\n",
    "\n",
    "        n = len(isConnected)\n",
    "        flag = [0] * n\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if flag[i] == 0:\n",
    "                count += 1\n",
    "                dfs(i)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        visited = [False]*n \n",
    "\n",
    "        def dfs(i):\n",
    "            for j in range(len(isConnected[i])):\n",
    "                if not visited[j] and isConnected[i][j] == 1:\n",
    "                    visited[j] = True\n",
    "                    dfs(j)\n",
    "\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                count += 1\n",
    "                visited[i] = True\n",
    "                dfs(i)\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
